package NC;

import java.util.*;

/**
 题目描述
 求给定的二叉树的前序遍历。
 例如：
 给定的二叉树为{1,#,2,3},

 返回：[1,2,3].
 备注；用递归来解这道题很简单，你可以给出迭代的解法么？
 如果你不明白{1,#,2,3}的含义，点击查看相关信息
 示例1
 输入
 复制
 {1,#,2,3}
 输出
 复制
 [1,2,3]
*/

class TreeNode {
    TreeNode(int val){
        this.val = val;
    }
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
}

//递归
class Solution1 {
    /**
     * @param root TreeNode类
     * @return int整型ArrayList
     */
    void dps(TreeNode root, ArrayList arrayList) {
        if (root == null) return;
        else {
            arrayList.add(root.val);
            dps(root.left,arrayList);
            dps(root.right,arrayList);

        } ;

    }

    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> ans = new ArrayList<>();
        dps(root,ans);
        return ans;

    }
}

//栈
class Solution12 {
    public ArrayList<Integer> preorderTraversal(TreeNode root){
        ArrayList<Integer> ans =new ArrayList<>();
        if(root==null) return ans;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()){
            TreeNode e = stack.pop();
            ans.add(e.val);
            if(e.right!=null){
                stack.push(e.right);
            }
            if(e.left!=null){
                stack.push(e.left);
            }
        }
        return ans;
    }
}